#include "backtrack.h"

BackTrack::BackTrack() {} //无参构造函数
	
BackTrack::BackTrack(const Application& thisApp) //有参 拷贝构造函数
{
	this->app = thisApp;
}

bool BackTrack::backTrack(const Position& currPos) //send a pos into bt
{
	app.progress(currPos);

	if (app.success(currPos)) 
		return true;

	else
	{
		Application::Iterator itr(currPos); 

		Position nextPos;

		while (!itr.noNextPosition()) 
		{
			nextPos = itr.getNextPosition(); //移动迭代器
			if (app.isValid(nextPos) && backTrack(nextPos)) //recursive call if valid
				return true; 
		}
		//cannot reach goal from currPos
		app.goBack(currPos); //backtrack 
		return false; //from currPos, no solution  :( 
	}
}